package automata;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.Stack;

public class Automata {

    private int count;
	private Set<State> states;

	public Automata() {
	    this.count = 0;
		this.states = new HashSet<State>();
	}
	
	public Automata(char character) throws Exception {
	    this();
	    int state0 = this.addInitialState(false);
        int state1 = this.addState(true);
        this.addTransition(state0, character, state1);
	}
	
	static public Automata wildcard() throws Exception{
		Automata a = new Automata();
		int state0 = a.addInitialState(false);
		int state1 = a.addState(true);
		a.addWildcardTransition(state0, state1);
		return a;
	}

	public int addInitialState(boolean isAlsoFinal) throws Exception {
	    int stateId = this.count;

		if (this.getInitialState() != null)
			throw new Exception("El Automata ya tiene un estado inicial");
		else
			this.states.add(new State(true, isAlsoFinal, stateId));

		this.count++;
		return stateId;
	}

	public int addState(boolean isFinal) {
	    int stateId = this.count;
	    this.states.add(new State(false, isFinal, stateId));
	    this.count++;
	    return stateId;
	}

	private State getInitialState() {
	    State initialState = null;
	    Iterator<State> it = this.states.iterator();
        boolean found = false;

        while (it.hasNext() && !found) {
            State anState = (State) it.next();
            if (anState.isInitial()) {
                initialState = anState;
                found = true;
            }
        }

        return initialState;
	}

	public int getInitialStateId() {
        return this.getInitialState().getId();
	}

	public void setInitialState(int stateId) throws Exception {
	    State newInitialState = this.getState(stateId);

	    if ( newInitialState == null) {
	        throw new Exception("No existe un estado con ID = " + String.valueOf(stateId));
	    }
	    else {
	        State initialState = this.getInitialState();
	        initialState.setInitial(false);
	        newInitialState.setInitial(true);
	    }
	}

	private State getState(int id) {
	    State result = null;
        Iterator<State> it = this.states.iterator();
        boolean found = false;

        while (it.hasNext() && !found) {
            State anState = (State) it.next();
            if (anState.getId() == id) {
                result = anState;
                found = true;
            }
        }

	    return result;
	}

	public Set<Integer> getFinalStates() {
		Set<Integer> finalStates = new HashSet<Integer>();
		Iterator<State> it = this.states.iterator();

		while (it.hasNext()) {

			State s = (State) it.next();
			if (s.isFinal()) {finalStates.add(new Integer(s.getId()));}
		}

		return finalStates;
	}

	public void addLambdaTransition(int originId, int destinyId) throws Exception {

	    State origin = this.getState(originId);
	    State destiny = this.getState(destinyId);

	    if (origin == null || destiny == null) {
	        throw new Exception("Tanto origen como destino deben ser estados existentes");
	    }
	    else {
            origin.addLambdaTransition(destiny);
	    }
	}

	public void addTransition(int originId, char value, int destinyId) throws Exception {

	    State origin = this.getState(originId);
	    State destiny = this.getState(destinyId);

	    if (origin == null || destiny == null) {
	        throw new Exception("Tanto origen como destino deben ser estados existentes");
	    }
	    else
	    	origin.addTransition(value, destiny);
	    
	}
	
	public void addWildcardTransition(int originId, int destinyId) throws Exception {

	    State origin = this.getState(originId);
	    State destiny = this.getState(destinyId);

	    if (origin == null || destiny == null) {
	        throw new Exception("Tanto origen como destino deben ser estados existentes");
	    }
	    else {
	    	for(Character symbol: this.getAlphabet())
	    		origin.addTransition(symbol, destiny);
	    }
	}

	private Set<Character> getAlphabet() {
		Character symbol = 'a';
		Set<Character> alphabet = new HashSet<Character>();
		while(symbol <= 'z') {
			alphabet.add(symbol);
			symbol++;
		}
		symbol = 'A';
		while(symbol <= 'Z') {
			alphabet.add(symbol);
			symbol++;
		}
		symbol = '0';
		while(symbol <= '9') {
			alphabet.add(symbol);
			symbol++;
		}
		alphabet.add(' ');
		return alphabet;
	}

	public void concatenation(Automata a, Automata b) throws Exception {
//		int initB = b.getInitialState().getId();
		this.states.addAll(a.states);
		this.count = a.count;
        State initialStateB = b.getInitialState();
        initialStateB.setInitial(false);  // dejamos al aut. 'b' sin estado inicial
                                          // ya que s�lo mantenemos el estado inicial
                                          // del aut. 'a'
		Iterator<State> statesIterator = b.states.iterator();
		while (statesIterator.hasNext()) {            // actualizamos los id's del aut. 'b'
			State s = statesIterator.next();
			s.setId(this.count);
			this.count++;
		}
		this.states.addAll(b.states);
		Iterator<Integer> finalStatesIterator = a.getFinalStates().iterator();
		while (finalStatesIterator.hasNext()) {
			Integer s =  finalStatesIterator.next();
			this.getState(s.intValue()).setFinal(false);
			this.addLambdaTransition(s.intValue(), initialStateB.getId());
		}
	}

	public void union(Automata a, Automata b) throws Exception {
		this.states.addAll(a.states);
		this.count = a.count;
        State initialStateA = a.getInitialState();
        State initialStateB = b.getInitialState();
        initialStateB.setInitial(false);  // dejamos al aut. 'b' sin estado inicial
                                          // ya que el proximo setInitialState() s�lo
                                          // va a 'desinicializar' al estado inicial
                                          // del aut. 'a'
		Iterator<State> it = b.states.iterator();
		while (it.hasNext()) {            // actualizamos los id's del aut. 'b'
			State s = (State) it.next();
			s.setId(this.count);
			this.count++;
		}
		this.states.addAll(b.states);
		int newInit = this.addState(false);
		this.setInitialState(newInit);
		this.addLambdaTransition(newInit, initialStateA.getId());
		this.addLambdaTransition(newInit, initialStateB.getId());
	}

	public void kleeneClosure() throws Exception {
		this.positiveClosure();
		State e = this.getInitialState();
		int e0 = this.addState(true);
		this.setInitialState(e0);
		this.addLambdaTransition(e0, e.getId());
	}

	public void positiveClosure() throws Exception {
		Set<Integer> finalStates = this.getFinalStates();
		Iterator<Integer> it = finalStates.iterator();
		State e0 = this.getInitialState();
		Integer e;

		while (it.hasNext()) {
			e = (Integer) it.next();
			this.addLambdaTransition(e.intValue(), e0.getId() );
		}
	}
	
	public void optional() throws Exception {
		int e0 = this.getInitialStateId();
        int e1 = this.addState(true);
        this.setInitialState(e1);
        this.addLambdaTransition(e1, e0);
	}

	public String show() {
		String result = "";
	    Iterator<State> statesIt = this.states.iterator();

	    while (statesIt.hasNext()) {
	        State anState = (State) statesIt.next();

	        if (anState.isInitial())
	            result += String.valueOf(anState.getId()) + " ! \n";
	        if (anState.isFinal())
	            result += String.valueOf(anState.getId()) + " # \n";

	        Iterator<Transition> transitionsIt = anState.getTransitions().iterator();
	        while (transitionsIt.hasNext()) {
	            Transition aTransition = (Transition) transitionsIt.next();
	            result += String.valueOf(aTransition.getOrigin().getId());
	            result += " ";
	            char value = aTransition.getValue();
	            result += String.valueOf(value);
	            result += " ";
	            result += String.valueOf(aTransition.getDestiny().getId());
	            result += " \n";
	        }
	    }

	    return result;
	}
	
	public boolean accept(String text) {
		State currentState = this.getInitialState(); 
		if(text.isEmpty() && currentState.isFinal())
			return true;
		int i = 0;
		while(i < text.length()) {
			Character symbol;
			symbol = text.charAt(i);
			
			if(currentState.hasTransitionFor(symbol)) {
				Transition transition = currentState.getTransitionFor(symbol);
				currentState = transition.getDestiny();
				if(transition.isLambda())
					throw new RuntimeException("El automata contine transiciones lambda. Convierta a deterministico el automata antes de ejecutarlo");
				i++;
				if((i == text.length()) && currentState.isFinal())
					return true;
			} else
				return false;
		}
		return false;
	}
	
	private HashSet<Integer> LambdaClosure(int e0){
		Stack<Integer> remaining = new Stack<Integer>();
		remaining.push(e0);
		HashSet<Integer> result = new HashSet<Integer>();
		result.add(e0);
		while(!remaining.empty()){
			int nextNode = remaining.pop();
			Set<Integer> lambdaNeighbours = this.getState(nextNode).getLambdaIds();
			for(Integer neighbour: lambdaNeighbours){
				if(!result.contains(neighbour)){
					result.add(neighbour);
					remaining.push(neighbour);
				}
			}
		}
		return result;
	}
	
	private HashSet<Integer> multipleLambdaClosure(Set<Integer> nodes){
		HashSet<Integer> result = new HashSet<Integer>();
		for(Integer node : nodes){
			result.addAll(LambdaClosure(node));
		}
		return result;
	}
	
	private HashSet<Integer> moveClosure(char c, Set<Integer> states){
		HashSet<Integer> result = new HashSet<Integer>();
		for(Integer state: states){
			result.addAll(multipleLambdaClosure(getState(state).getNeighboursFor(c)));
		}
		return result;
	}
	
	//Devuelve todos los caracteres que aparecen en alguna transicion
	//del automata (menos lambda, claro)
	private HashSet<Character> getAllChars(){
		HashSet<Character> result = new HashSet<Character>();
		for(State state: states){
			for(Transition trans: state.getTransitions()){
				if(!trans.isLambda()){
					result.add(trans.getValue());
				}
			}
		}
		
		return result;
	}
	
	//Devuelve true si uno o mas nodos del conjunto son finales
	private boolean containsFinalState(Set<Integer> states){
		for(Integer state: states){
			if (getFinalStates().contains(state)){
				return true;
			}
		}
		return false;
	}
	
	//Cuando se haga la conversion, cada nodo del AFD va a representar a algun subconjunto
	//de nodos del AFND de entrada
	public Automata convertToDfa() throws Exception{
		
		Automata result = new Automata();
		HashSet<Character> chars = getAllChars();
		chars.add('a');
		chars.add('b');
		//mapping que le asigna a subconjuntos de estados del AFND un numero de nodo
		HashMap<HashSet<Integer>, Integer> states = new HashMap<HashSet<Integer>, Integer>();
		//stack con los nodos del AFD que falta procesar
		Stack<HashSet<Integer>> statesRemaining = new Stack<HashSet<Integer>>();
		HashSet<Integer> currentStates= LambdaClosure(getInitialState().getId());
		HashSet<Integer> newStates= new HashSet<Integer>();
		int stateNumber = result.addInitialState(containsFinalState(currentStates));
		states.put(currentStates, stateNumber);
		statesRemaining.push(currentStates);
		while(!statesRemaining.isEmpty()){
			currentStates= statesRemaining.pop();
			for(Character car : chars ){
				//calcular los estados a los que se llega por el caracter car
				newStates = moveClosure(car, currentStates);
				if(!newStates.isEmpty()){
					//Si es la primera vez que se llega a este estado agregarlo al AFD
					if(!states.containsKey(newStates)){
						statesRemaining.push(newStates);
						stateNumber = result.addState(containsFinalState(newStates));
						states.put(newStates, stateNumber);
					}
					//Agregar la transicion al estado del AFD al que llegue por el caracter car
						result.addTransition(states.get(currentStates), car , states.get(newStates));
				}
			}
		}
		return result;
	}
}
